package 热题100;

public class 热题19删除链表的倒数第N个结点 {


    /**
     * 传入头节点，删除第n个节点后返回头节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        //先遍历节点的个数
        int count = 0;
        ListNode tem = head;
        while (tem != null){
            count++;
            tem = tem.next;
        }


        //如果就是要删除第一个节点，直接返回head的下一个节点
        if (count == n){
            return head.next;
        }

        //如果n大于链表的长度，返回null
        if (n > count){
            return null;
        }

        //找到节点个数,倒数第n个相当于顺数第count - n个
        int index = 0;
        ListNode prev =  new ListNode();
        prev.next = head;//要删除节点的前驱节点
        ListNode cur = head;//要删除的节点的位置。
        while (index < count - n){
            index++;
            prev.next = cur;
            prev = prev.next;
            cur = cur.next;
        }
        //index == count-n，表示找到了要删除的节点
        ListNode next = cur.next;
        prev.next = next;
        cur.next = null;

        return head;
    }

}
